home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Deutsche Edition 1
/
Deutsche Edition 1.iso
/
amok
/
031-040
/
amok32
/
ringbuffers
/
ringbuffers.dok
< prev
next >
Wrap
Text File
|
1993-11-04
|
8KB
|
199 lines
======================================================================
Dokumentation zu "RingBuffers" Version 1.2
Autor: Nicolas Benezan, Postwiesenstr. 2, D7000 Stuttgart 60
======================================================================
Übersicht
* Kopierrecht
* Umfang des Projekts
* Einleitung
* Beschreibung der Prozeduren
* Demo- / Testprogramm
Kopierrecht
Das komplette Projekt (Quelltext, Dokumentation und Objectcode) ist
Public Domain Software. Es darf beliebig kopiert und verbreitet werden
solange...
* mein Name und dieser Kopierrechtshinweis erhalten bleiben,
* die Vollständigkeit des ganzen Projekts gewährleistet ist, und
* mit dem Vertrieb dieser Software kein Gewinn erwirtschaftet wird.
Die Kommerzielle Nutzung ohne meine ausdrückliche schriftliche
Genehmigung ist untersagt (über Gewinnbeteiligung läßt sich reden).
W i c h t i g: Dies gilt insbesondere auch für "schwarze Schafe" der
"PD"-Versandhäuser, die ganz offensichtlich Gewinn machen, was z.B. durch
ganzseitige Anzeigen in Zeitschiften erkennbar ist.
Verbesserungsvorschläge sind stets willkommen. Falls Sie Veränderungen
am Programm vornehmen, dokumentieren Sie diese bitte gut verständlich.
Es würde mich freuen, wenn Sie mich über größere Veränderungen oder
Erweiterungen in Kenntnis setzen würden.
(c) 1988 by Nicolas Benezan.
Umfang des Projekts
Das komplette Projekt "RingBuffers" beinhaltet folgende Dateien:
* RingBuffers.dok Diese Dokumentation
* RingBuffers.def Quelltext der Definition
* RingBuffers.mod Quelltext der Implementation
* MultitaskDemo Demoprogramm für RingBuffers mit parallelen Prozessen
* SyncDemo Gegenbeispiel ohne RingBuffers
* MultitaskDemo.mod
* SyncDemo.mod Quelltexte der Demos
(Stand 12.Jan.1990)
Einleitung
Einen Ringpuffer kann man sich als in sich geschlossene Schleife von
Puffern vorstellen (* = voller Puffer, · = leerer Puffer):
Lesezugriff
|
· > - > * > * > * > * > *
^ v
· *
^ v
· < · < · < · < + < * < *
|
Schreibzugriff
Die Daten werden dabei wie in einer Art Warteschlange, die immer im Kreis
herum läuft, abgelegt. Am einen Ende werden immer Daten hinzugefügt, am
anderen Ende welche weggenommen. Der Ringpuffer kann auch als FIFO-Speicher
(First-In-First-Out) variabler aber endlicher Größe betrachtet werden.
Es gibt zwei Sonderfälle: Alle Puffer sind voll - in diesem Fall ist der
Schreibzugriff blockiert, oder alle Puffer sind leer - dann ist kein
Lesezugriff mehr möglich.
Ringpuffer kommen zum Einsatz, wenn bei zwei asynchron ablaufenden
Prozessen, die Ausgaben des einen als Eingabe für den anderen verwendet
werden (Produzent-Konsument-Problem). Der Ringpuffer dient dazu,
kurzzeitige Unterschiede des "Angebots" und der "Nachfrage" auszugleichen.
Die beiden Prozesse können so ungestört parallel ablaufen, ohne ständig auf
den jeweils anderen Prozess warten zu müssen. Lediglich bei den oben
genannten Sonderfällen treten Wartezeiten ein. Sie treten um so häufiger
auf, je schneller ein Prozess im Vergleich zum anderen ist, bzw. je
geringer das Fassungsvermögen des Ringpuffers ist.
Eine denkbare Anwendung für Ringpuffer wäre z.B. ein PIPE-Handler.
Beschreibung der Prozeduren
CreateRingBuffer
----------------
dient zum Erzeugen eines Ringpuffers. Als Parameter werden die Anzahl der
Datenblöcke, aus denen sich der Ringpuffer zusammensetzt, und deren Größe
angegeben. Außerdem müssen noch zwei Signale, FullSignal und EmptySignal,
sowie zwei TaskPtr angegeben werden, deren Bedeutung später noch erläutert
wird.
DiscardRingBuffer
-----------------
löscht einen Ringpuffer aus dem Speicher.
GetEmptyBlock
-------------
gibt die Adresse des nächsten leeren Blocks zurück (der Block, der sich
neben dem vollen Block mit den "jüngsten" Daten befindet), und sperrt ihn
für weitere Zugriffe.
GetFullBlock
------------
gibt die Adresse des nächsten vollen Blocks (der Block mit den
"ältesten" Daten) zurück, und sperrt den Block für weitere Zugriffe.
PutFullBlock
------------
gibt einen beschriebenen ("gefüllten") Block für Lesezugriffe frei.
PutEmptyBlock
-------------
gibt einen gelesenen ("geleerten") Block für Schreibzugriffe frei.
AllBlocksFull, AllBlocksEmpty
-----------------------------
erlauben das Feststellen der oben genannten Sonderfälle. Eigentlich müßten
die Prozeduren "NoMoreEmptyBlocks" und "NoMoreFullBlocks" heißen. Wenn
AllBlocksFull() = TRUE ist, bedeutet daß nämlich nicht unbedingt, daß
wirklich alle Puffer (Blöcke) voll sind, sondern nur, daß es keine leeren
Puffer mehr gibt. Es ist ja auch möglich, daß ein Block gerade noch
beschrieben wird, also "halb"-voll ist. Wir wollen jedoch keine
Haarspalterei betreiben und einigen uns darauf, daß wenn AllBlocksFull()
= TRUE ist, kein Schreibzugriff mehr möglich ist.
Behandlung der Sonderfälle
Man muß natürlich nicht vor jedem GetEmptyBlock() abfragen ob
AllBlocksFull() sind und umgekehrt. Dazu hat GetEmptyBlock() und
GetFullBlock() einen Resultatstyp BOOLEAN, der FALSE wird, wenn die
entsprechende Operation nicht möglich war.
Wenn nun ein Prozess blockiert wird, weil keine vollen oder leeren Puffer
mehr verfügbar sind, woher weiß der Prozess, wann er wieder weitermachen
kann?
Hierzu dienen die Signale, die man von CreateRingBuffer bekommt. Jedes
PutFullBlock() löst ein FullSignal aus, und jedes PutEmptyBlock() löst ein
EmptySignal aus. Zu beachten ist, daß erst auf ein Signal gewartet werden
darf, wenn GetEmpty- oder GetFullBlock() fehlgeschlagen ist, oder wenn
durch AllBlocksFull() bzw. AllBlocksEmpty() die Notwendigkeit des Wartens
festgestellt wurde. Vorher ist der Zustand der Signale undefiniert.
FALSCH:
SigSet:= Exec.Wait (FullSignal);
Ok:= GetFullBlock (Buffer, Block, DataPtr);
RICHTIG:
WHILE NOT GetFullBlock (Buffer, Block, DataPtr) DO
SigSet:= Exec.Wait (FullSignal);
END;
V O R S I C H T !!! Signale sind nur für den Task gültig, in dem sie mit
Exec.AllocSignal() alloziert wurden! D.h. NUR DER Task, der FullSignal
alloziert hat, darf auch auf das Signal warten, und GENAU DIESER Task muß
auch als Parameter "FullSigTask" bei CreateRingBuffer() angegeben werden!!!
Zu warnen ist auch vor Deadlock-Situationen, bei denen beide Prozesse
aufeinander warten und nichts mehr geschieht. Prüfen Sie Ihr Programm
sorfältig auf Korrektheit!
Für Fortgeschrittene: Zu bemerken ist, daß FullSigTask und EmptySigTask
auch identisch sein können (!). Allerdings darf dann nicht mit Exec.Wait()
gewartet werden (sonst ist die Ausführungszeit unter Umständen nicht
endlich... ). Quasi-parallel ablaufende Prozesse können auch mit Coroutinen
oder Task-Exceptions realisiert werden.
Demo- / Testprogramm
Folgende Demoprogramme sind in diesem Projekt enthalten:
* SyncDemo:
Zeigt mit einer Art Balkendiagramm die absolute (schwarz) und relative
(weiß) Häufigkeit einzelner Zeichen einer Datei an. Diese Demo zeigt nur
den Unterschied zu den anderen Demos und verwendet weder RingBuffers noch
parallele Prozesse.
Deutlich zu sehen ist der ruckartige Aufbau der Grafik, die durch das
erforderliche Warten auf das Nachladen von Diskette verursacht wird.
(Starten des Prgs: Click auf SyncDemo, Doppelclick auf bel. File)
* MultitaskDemo:
Erzeugt die gleiche Grafik, aber unter Zuhilfenahme von RingBuffers und
parallel laufenden Tasks. Dies ist gleichzeitig ein Demoprogramm für das
Modul "TaskSupport", das auf dieser Diskette in einem extra Projekt
gesondert dokumentiert ist.